This invention relates generally to intra-class, per-connection schedulers for digital link systems, such as aysnchronous transfer mode (ATM) telecommunications systems, and more particularly, provides a novel scheduler implementing weighted fair queuing by a weight limited first in-first out methodology.
Information regarding ATM systems can be found in the ATM Forum, xe2x80x9cATM User-Network Interface Specification,xe2x80x9d Version 3.1, September, 1994, and in Martin de Prycker, xe2x80x9cAsynchronous Transfer Mode: Solution for Broadband ISDN,xe2x80x9d Ellis Horwood, N.Y. 1993, both of which are incorporated herein by reference. Aspects of ATM Systems are disclosed in U.S. Pat. Nos. 5,818,815, 5,794,025, and 5,768,259, also incorporated herein by reference.
An advantage of high bandwidth, fixed length cell based transfer mode techniques, such as ATM, Frame Relay, IP, etc., is the capability of high-speed, low-delay multiplexing and switching of different types of user information trafficxe2x80x94including data, voice, image and videoxe2x80x94over the same network, while optimizing bandwidth and resource utilization. In ATM connection-oriented networks, the end-to-end traffic of data for one user, between the source and the destination, is represented by a virtual connection (VC). Several VCs can be grouped into a virtual path (VP) that can be switched as a unit.
An ATM system segments user traffic into fixed-length cells. A header in each cell typically includes a virtual channel identifier (VCI) and a virtual path identifier (VPI) associated with the corresponding cell. The VCI and VPI fields together identify a virtual channel connection that is established when a user requests a network connection in an ATM system. The allocation of available transmission opportunities or slots to user traffic cells is generally referred to as cell scheduling. Devices that accomplish this task are called schedulers.
In a data communication system, such as an ATM system, data can optimally be differentiated by classes (e.g., voice, video, data, and other digital signals). A class scheduler allocates opportunities to the different classes, generally by strict priority or some variation thereof which may incorporate some minimum guarantees to each class. Opportunities, once allocates to a class, must be allocated to connections within the class by a second-order scheduler. A scheduler which operates in this manner is called an intra-class scheduler. An intra-class, per-connection scheduler (i) monitors the status of an input queue for each connection in a given class of service; and (ii) according to some pre-defined criteria, makes decisions about the connection to be serviced at the next transmission opportunity. A digital switching apparatus utilizes these decisions to select a connection for the next transmission opportunity.
The same scheduler can also be used to allocate opportunities of one connection to multiple sub connections according to some pre-defined criteria. Such behavior can be used to schedule virtual channel connections (VCCs) into a virtual path connection (VPC). A scheduler which operates in this manner is called a sub-connection scheduler.
The intra-class per-connection scheduler thus enables the digital link system to determine which connection will utilize the next share of limited bandwidth or processor resources. These decisions are important to the performance of bandwidth-limited digital link systems. Scheduling at the intra-class level of per-connection queues is a major problem to be resolved in cell-based networks.
At the intra-class scheduler level a goal of scheduling is to ensure fairness within a particular class (i.e. attempting to provide transmission opportunities for an equal amount of data for each user while taking into account the relative amount of bandwidth required or subscribed to by a user, that is, that user""s xe2x80x9csharexe2x80x9d). A goal of scheduling is to provide fair access to that share without adding unnecessary delay into the system.
A conventional scheduling algorithm utilized is a Round Robin algorithm. In Round Robin the scheduler polls, or inspects the queue belonging to the connection of each user in a round robin fashion (i.e. one at a time in a predefined repeating order).
There are several disadvantages to the Round Robin algorithm. The scheduler visits the queue belonging to the connection of each user without taking into account the amount of bandwidth to which that user subscribes and/or the amount of data that connection is transmitting. Another disadvantage is that a cell may be required to wait in a per connection queue while the scheduler polls all other per connection queues before that queue is inspected by the scheduler (even if that queue is the only queue attempting to transmit data). Moreover, the length of time a cell must wait is a function of chance. For example, a cell may arrive in a particular per connection queue just as the Round Robin scheduler is about to inspect that queue for available cells, in which case that cell will encounter a relatively low transit delay. However, another cell from the same connection may arrive just after that per connection queue has been inspected (visited), in which case that cell will encounter a relatively high transit delay. Thus, the cell delay variation (CDV) through a Round Robin scheduler is high.
Since CDV is a significant constraint in system design, and since many factors that contribute to CDV are beyond the control of the system design, it is very important that any algorithm designed to ensure fairness does not unnecessarily increase CDV, as the Round Robin algorithm does.
An improvement to the Round Robin system includes the weighted burst Round Robin algorithm. In weighted burst Round Robin the number of contiguous cell opportunities that a connection can utilize when the queue for that connection is polled is dependent upon the relative weight of that connection. Thus, when a connection""s queue is polled by the scheduler, the most that connection can transmit is the number of cells equal to its weight (i.e. the connection can send a xe2x80x9cburstxe2x80x9d of data). Although this algorithm provides a more flexible definition of fairness than the Round Robin, due to its burst nature, the possibility of increased CDV is even greater. In the Round Robin, a maximum of one cell of a user""s data is sent when the queue belonging to their connection is visited. However, in the weighted burst Round Robin, a connection of high relative weight can monopolize all cell opportunities for that class for a significant length of time.
Another conventional improvement to the Round Robin algorithm is the weighted interleaved Round Robin algorithm. In this algorithm, connections with a weight greater than 1 are allocated more than one position in the Round Robin pattern. Thus, rather than a single position with multiple cell transmit opportunities, a connection may be provided with multiple smaller bandwidth positions which combined provide the same transmit opportunities spread out over different positions. In this sense, the burst will be spread out over time, somewhat reducing the additional CDV introduced into the system. Unfortunately, some additional CDV is still introduced, which remains a function of chance as to when a cell arrives relative to the inspection of the per connection queue. Further, a weighted interleaved Round Robin algorithm is complex to implement.
Accordingly, a need exists for providing intra-class level scheduling on a weighted fair basis, while limiting the amount of additional CDV introduced to the system.
It is thus an object of the invention to provide relatively low-cost, relatively simple and efficient scheduling mechanisms. It is another object of the invention to provide such mechanisms which minimize the introduction of additional CDV and which provide weighted fairness among connections. It is yet another object of this invention to provide a first in-first out (FIFO) mechanism that preserves the cell arrival order, so that a connection can expect it""s cell to be sent in the order upon which it is received by a single common queue.
These and other objects are attained by the invention, which in one aspect provides a method of scheduling a plurality of data flows within a class of service for digital traffic over a limited bandwidth outgoing datapath. The method includes establishing a FIFO order for scheduling of data flow through a single common queue feeding this datapath, limiting a connection""s access to this single common queue when the number of cells in the single common queue belonging to this connection has reached the integer weight value for that connection, storing an overflow of the data from the connection in a per connection queue, and moving data from a per connection queue into the common queue when an equivalent of data belonging to that connection has been removed from the common queue and sent over the outgoing datapath. The integer weight value for a connection is not fixed, but may vary to take into account an increase or decrease in the number of connections.
The method of the invention also includes further establishing a FIFO order for scheduling of data flow through a tributary single common queue feeding a connection, limiting access by a sub-connection to this tributary single common queue when the number of cells in the tributary single common queue belonging to the sub-connection has reached the integer weight value for that sub-connection, storing an overflow of the data from that sub-connection in a per sub-connection queue, and moving data from a per sub-connection queue into the tributary common queue when an equivalent of data belonging to that sub-connection has been removed from the tributary common queue and sent to the connection. The integer weight value of a sub-connection is not fixed, but may vary to take into account an increase or decrease in the number of sub-connections.
In another embodiment, the invention includes a scheduler for a digital link system which schedules multiple data flows over a limited bandwidth outgoing datapath and within a class of service for digital traffic. The scheduler includes a single common queue configured as a FIFO queue. It also includes a per connection FIFO queue coupled to the single common queue and configured to receive an overflow of data from the single common queue, wherein the overflow includes data transmitted from a connection to the single common queue in excess of an integer weight value for the connection.
The scheduler of the invention also includes a tributary single common queue configured as a FIFO queue, and a per sub-connection queue coupled to the tributary single connection queue and configured to receive an overflow of data from the tributary single connection queue, wherein said overflow includes data transmitted from a sub-connection to the tributary single connection queue in excess of an integer weight value for the sub-connection.
The invention will now be described in connection with certain exemplary embodiments; however, it should be clear to those skilled in the art that various modifications, additions and subtractions can be made without departing from the spirit or scope of the invention and the claims herein.